{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# FM问题来源\n",
    "\n",
    "\n",
    "CTR/CVR预测时，用户的性别、职业、教育水平、品类偏好，商品的品类等，经过One-Hot编码转换后都会导致样本数据的稀疏性。\n",
    "\n",
    "特别是商品品类这种类型的特征，如商品的末级品类约有550个，采用One-Hot编码生成550个数值特征，但每个样本的这550个特征，有且仅有一个是有效的（非零）。\n",
    "\n",
    "由此可见，数据稀疏性是实际问题中不可避免的挑战。\n",
    "\n",
    "One-Hot编码的另一个特点就是导致特征空间大。\n",
    "\n",
    "例如，商品品类有550维特征，一个categorical特征转换为550维数值特征，特征空间剧增。\n",
    "\n",
    "同时通过观察大量的样本数据可以发现，某些特征经过关联之后，与label之间的相关性就会提高。例如，“USA”与“Thanksgiving”、“China”与“Chinese New Year”这样的关联特征，对用户的点击有着正向的影响。\n",
    "\n",
    "换句话说，来自“China”的用户很可能会在“Chinese New Year”有大量的浏览、购买行为，而在“Thanksgiving”却不会有特别的消费行为。\n",
    "\n",
    "这种关联特征与label的正向相关性在实际问题中是普遍存在的，如“化妆品”类商品与“女”性，“球类运动配件”的商品与“男”性，“电影票”的商品与“电影”品类偏好等。\n",
    "\n",
    "因此，引入两个特征的组合是非常有意义的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# FM基本原理\n",
    "\n",
    "\n",
    "多项式模型是包含特征组合的最直观的模型。\n",
    "\n",
    "在多项式模型中，特征 $x_i$ 和 $x_j$ 的组合采用 $x_ix_j$表示，即 $x_i$ 和 $x_j$ 都非零时，组合特征 $x_ix_j$ 才有意义。\n",
    "\n",
    "从对比的角度，本文只讨论二阶多项式模型。模型的表达式如下\n",
    "\n",
    "$$y(x) = w_0+ \\sum_{i=1}^n w_i x_i + \\sum_{i=1}^n \\sum_{j=i+1}^n w_{ij} x_i x_j  \\tag{1}$$\n",
    "\n",
    "其中，$n$ 代表样本的特征数量，$x_i$ 是第 $i$ 个特征的值，$w_0$、$w_i$、$w_{ij}$是模型参数。\n",
    "\n",
    "从公式(1)可以看出，组合特征的参数一共有 $\\frac{n(n−1)}{2}$个，任意两个参数都是独立的。\n",
    "\n",
    "然而，在数据稀疏性普遍存在的实际应用场景中，二次项参数的训练是很困难的。\n",
    "\n",
    "其原因是，每个参数 $w_{ij}$的训练需要大量 $x_i$ 和 $x_j$ 都非零的样本；\n",
    "\n",
    "由于样本数据本来就比较稀疏，满足“$x_i$ 和 $x_j$ 都非零”的样本将会非常少。\n",
    "\n",
    "训练样本的不足，很容易导致参数 $w_{ij}$ 不准确，最终将严重影响模型的性能。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 系数矩阵分解\n",
    "\n",
    "\n",
    "那么，如何解决二次项参数的训练问题呢？矩阵分解提供了一种解决思路。\n",
    "\n",
    "与在model-based的协同过滤中，一个rating矩阵可以分解为user矩阵和item矩阵。\n",
    "\n",
    "对于对称矩阵W，\n",
    "$$W=\n",
    "        \\begin{pmatrix}\n",
    "        \\omega_{11} & \\omega_{12}& ... &\\omega_{1n} \\\\\n",
    "        \\omega_{21} & \\omega_{22}& ... &\\omega_{2n} \\\\\n",
    "        \\vdots &\\vdots &\\ddots &\\vdots\\\\\n",
    "       \\omega_{n1} & \\omega_{n2}& ... &\\omega_{nn} \\\\\n",
    "        \\end{pmatrix}_{n\\times n}$$\n",
    "\n",
    "由于直接求解W不方便，因此我们引入隐变量V： \n",
    "$$V=\n",
    "        \\begin{pmatrix}\n",
    "        v_{11} & v_{12}& ... &v_{1k} \\\\\n",
    "        v_{21} & v_{22}& ... &v_{2k} \\\\\n",
    "        \\vdots &\\vdots &\\ddots &\\vdots\\\\\n",
    "       v_{n1} & v_{n2}& ... &v_{nk} \\\\\n",
    "        \\end{pmatrix}_{n\\times k}=\\begin{pmatrix} \n",
    "V_1^T\\\\\n",
    "V_2^T\\\\\n",
    "\\cdots \\\\\n",
    "V_n^T\\\\\n",
    "\\end{pmatrix}$$\n",
    "\n",
    "满足\n",
    "$$VV^T = W$$\n",
    "\n",
    "$V$ 的第$ j$列$v_j$便是第$ j $维特征的**隐向量**。换句话说，每个参数 $w_{ij}=⟨v_i,v_j⟩$，这就是FM模型的核心思想。因此，FM的模型方程为（本文不讨论FM的高阶形式）\n",
    "\n",
    "$$y(x) = w_0+ \\sum_{i=1}^n w_i x_i + \\sum_{i=1}^n \\sum_{j=i+1}^n<v_i, v_j >x_i x_j \\tag{2}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 参数个数\n",
    "\n",
    "\n",
    "$ v_i  $是第 $ i $ 维特征的隐向量，$ <·,·> $ 代表向量点积。\n",
    "\n",
    "隐向量的长度为 $ k （ k << n $），包含 $ k $ 个描述特征的因子。\n",
    "\n",
    "根据公式2，二次项的参数数量减少为 $ kn $个，远少于多项式模型的参数数量。\n",
    "\n",
    "另外，参数因子化使得 $ x_h x_i $ 的参数和 $ x_i x_j $ 的参数不再是相互独立的，因此我们可以在样本稀疏的情况下相对合理地估计FM的二次项参数。\n",
    "\n",
    "具体来说，$ x_h x_i $ 和 $ x_i x_j $ 的系数分别为 $ <v_h,v_i> $ 和 $ <v_i, v_j>$，它们之间有共同项 $ v_i $。\n",
    "\n",
    "也就是说，所有包含“$ x_i $ 的非零组合特征”（存在某个 $ j\\neq i $，使得 $ x_i x_j \\neq 0 $）的样本都可以用来学习隐向量 $ v_i $，这很大程度上避免了数据稀疏性造成的影响。\n",
    "\n",
    "而在多项式模型中，$ w_{hi} $ 和 $ w_{ij} $ 是相互独立的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 预测时间复杂度\n",
    "\n",
    "显而易见，公式(2)是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy损失来求解分类问题。\n",
    "\n",
    "当然，在进行二元分类时，FM的输出需要经过sigmoid变换，这与Logistic回归是一样的。\n",
    "\n",
    "当我们已经求出所有参数以后，对新输入对象进行预测时，FM的计算复杂度是 $O(kn^2)$。\n",
    "\n",
    "但是，通过公式(3)的等式，FM的二次项可以化简，其复杂度可以优化到 $O(kn)$。\n",
    "\n",
    "由此可见，**FM可以在线性时间对新样本作出预测**。\n",
    "\n",
    "$$\\sum_{i=1}^n \\sum_{j=i+1}^n \\langle \\mathbf{v}_i, \\mathbf{v}_j \\rangle x_i x_j = \\frac{1}{2} \\sum_{f=1}^k \\left(\\left( \\sum_{i=1}^n v_{i, f} x_i \\right)^2 - \\sum_{i=1}^n v_{i, f}^2 x_i^2 \\right) \\tag{3}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 梯度下降法\n",
    "\n",
    "\n",
    "利用SGD（Stochastic Gradient Descent）训练模型。模型各个参数的梯度如下\n",
    "\n",
    "$$\\frac{\\partial}{\\partial\\theta} y (\\mathbf{x}) = \\left\\{\\begin{array}{ll} 1,            & \\text{if}\\; \\theta\\; \\text{is}\\; w_0 \\\\ x_i,         & \\text{if}\\; \\theta\\; \\text{is}\\; w_i \\\\ x_i \\sum_{j=1}^n v_{j, f} x_j - v_{i, f} x_i^2,  & \\text{if}\\; \\theta\\; \\text{is}\\; v_{i, f} \\end{array}\\right.$$\n",
    "\n",
    "\n",
    "其中，$ v_{j, f} $ 是隐向量 $ v_j $ 的第 $ f $ 个元素。\n",
    "\n",
    "由于 $ \\sum_{j=1}^n v_{j, f} x_j $ 只与 $ f $ 有关，而与 $ i $ 无关，在每次迭代过程中，只需计算一次所有 $ f $ 的 $ \\sum_{j=1}^n v_{j, f} x_j $，就能够方便地得到所有 $ v_{i, f} $ 的梯度。\n",
    "\n",
    "显然，计算所有 $ f $ 的 $ \\sum_{j=1}^n v_{j, f} x_j $ 的复杂度是 $ O(kn) $；\n",
    "\n",
    "已知 $ \\sum_{j=1}^n v_{j, f} x_j $ 时，计算每个参数梯度的复杂度是 $ O(1) $；\n",
    "\n",
    "得到梯度后，更新每个参数的复杂度是 $ O(1) $；模型参数一共有 $ nk + n + 1 $ 个。\n",
    "\n",
    "因此，FM参数训练的复杂度也是 $ O(kn) $。综上可知，FM可以在线性时间训练和预测，是一种非常高效的模型。\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
